class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 递归
# class Solution(object):
#     def reverseList(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         if not head:
#             return None
#
#         def search(node):
#             if not node.next:
#                 return node, node
#             first, last = search(node.next)
#             last.next = node
#             last = node
#             node.next = None
#             return first, last
#
#         return search(head)[0]

# 迭代
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        prev = head
        node = head.next
        prev.next = None
        while node:
            next_node = node.next
            node.next = prev
            prev = node
            node = next_node
        return prev
